package sort

//https://blog.csdn.net/bdss58/article/details/78388858
const (
	UINT_MIN uint = 0
	//^既可以是二元运算符，也可以是一元运算符:按位取反(对于无符号常量，掩码全为1，对于有符号和无类型常量，掩码全为-1。)
	//https://golang.org/ref/spec
	//https://studygolang.com/articles/9225
	UINT_MAX uint = ^uint(0)            //全为1
	INT_MIN  int  = ^int(^uint(0) >> 1) //右移的目的: 有符号数高位是符号位，无符号转成有符号需要将高位变成0，相当于除以2。根据补码，其最小值二进制表示，首位1，其余0
	INT_MAX  int  = ^INT_MIN            //根据补码，其最大值二进制表示，首位0，其余1
)

//归并排序
//https://www.cnblogs.com/ghj1976/archive/2013/02/28/2937319.html
func MergeSort(arr []int) {
	MergeSorthelper(arr, 0, len(arr)-1)
}

func MergeSorthelper(arr []int, start int, end int) {
	if start < end {
		mid := (start + end) / 2
		//递归
		MergeSorthelper(arr, start, mid)
		MergeSorthelper(arr, mid+1, end)
		//合并
		merge2(arr, start, mid, end)
	}
}

//该函数是合并两个已经排好序的序列
//A是一个数组，p,q和r是数组下标，满足 p<=q<=r。下面的函数假设子数组 A[p…q] 和 A[q+1...r]都是已经拍好序的。
func merge(A []int, p int, q int, r int) {
	leftLen := q - p + 1
	rightLen := r - q

	arrLeft := make([]int, leftLen+1)
	arrRight := make([]int, rightLen+1)
	var i int
	for i = 0; i < leftLen; i++ {
		arrLeft[i] = A[i+p]
	}
	arrLeft[leftLen] = INT_MAX //哨兵牌

	for i = 0; i < rightLen; i++ {
		arrRight[i] = A[i+q+1]
	}
	arrRight[rightLen] = INT_MAX //哨兵牌

	var left, right, k int = 0, 0, p
	//因为哨兵牌的存在，两边数组不会提前遍历结束，除非都是哨兵牌
	for ; k <= r; k++ {
		if arrLeft[left] <= arrRight[right] {
			A[k] = arrLeft[left]
			left++ //左指针自增
		} else {
			A[k] = arrRight[right]
			right++ //右指针自增
		}
	}
}

//不用哨兵牌的方法
func merge2(A []int, p int, q int, r int) {
	leftLen := q - p + 1
	rightLen := r - q

	arrLeft := make([]int, leftLen)
	arrRight := make([]int, rightLen)
	for i := 0; i < leftLen; i++ {
		arrLeft[i] = A[i+p] //偏移量
	}
	for i := 0; i < rightLen; i++ {
		arrRight[i] = A[i+q+1] //偏移量,右侧不含q本身
	}

	//不能用切片切割来做，原因是切片切割后共享原切片数据
	// leftArr := arr[low:mid+1]
	// rightArr := arr[mid+1:high+1]

	var left, right, k int = 0, 0, p
	//没有哨兵牌，就需要注意循环要满足条件：如果左右两侧数组都有元素
	for ; left < leftLen && right < rightLen && k <= r; k++ {
		if arrLeft[left] <= arrRight[right] {
			A[k] = arrLeft[left]
			left++ //左指针自增
		} else {
			A[k] = arrRight[right]
			right++ //右指针自增
		}
	}

	//如果左数组还有剩余
	for ; left < leftLen && k <= r; k++ {
		A[k] = arrLeft[left]
		left++
	}

	//如果右数组还有剩余
	for ; right < rightLen && k <= r; k++ {
		A[k] = arrRight[right]
		right++
	}
}
